/**
 * 一只青蛙一次可以跳上1级台阶,也可以跳上2级,
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
 */

/**
 * 动态规划:
 * 1.定义状态
 * 2.编写状态转移方程
 * 3.设置初始值
 */
public class suanfa09 {
    //f(n):青蛙跳上第n 级台阶的总跳法数  定义状态
    //f(n)=f(n-1) + f(n-2)           编写状态方程
    //f(0)=1  f(1)=1 f(2)=2          设置初始值
    public int JumpFloor1(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 2; i <= target; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target];
    }
    public int JumpFloor2(int target) {
        int first = 1;
        int second = 1;
        int third = 1;
        for (int i = 2; i <= target; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
}
